package main

import (
	"fmt"
	"sort"
)

func findX(arr []int, x int) int {
	i := 0
	j := len(arr) - 1
	for i <= j {
		mid := i + (j-i)/2
		if arr[mid] == x {
			return mid
		} else if arr[mid] < x {
			i = mid + 1
		} else {
			j = mid - 1
		}
	}
	if i > 0 {
		i--
	}
	return i
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func findClosestElements(arr []int, k int, x int) []int {
	i := findX(arr, x)
	j := i + 1
	result := make([]int, 0, k)
	for len(result) < k {
		if i < 0 || i >= len(arr) {
			result = append(result, arr[j])
			j++
		} else if j < 0 || j >= len(arr) {
			result = append(result, arr[i])
			i--
		} else {
			diffI := abs(arr[i] - x)
			diffJ := abs(arr[j] - x)
			if diffI <= diffJ {
				result = append(result, arr[i])
				i--
			} else {
				result = append(result, arr[j])
				j++
			}
		}
	}
	sort.SliceStable(result, func(i, j int) bool {
		return result[i] < result[j]
	})
	return result
}

func main() {
	var ret []int
	ret = findClosestElements([]int{0, 0, 1, 2, 3, 3, 4, 7, 7, 8}, 3, 5)
	fmt.Printf("%#v\n", ret)
	ret = findClosestElements([]int{1, 2, 3, 4, 5}, 4, 3)
	fmt.Printf("%#v\n", ret)
	ret = findClosestElements([]int{1, 2, 3, 4, 5}, 4, -1)
	fmt.Printf("%#v\n", ret)
	ret = findClosestElements([]int{1, 2, 3, 4, 5}, 4, 6)
	fmt.Printf("%#v\n", ret)
	ret = findClosestElements([]int{2, 4, 6, 9, 10}, 3, 7)
	fmt.Printf("%#v\n", ret)
}
